package algotithm.leetcode.dfs.test1631;

/**
 * @author zhouyanxiang
 * @Date 2021-01-2021/1/29-10:18
 * @Title 1631. 最小体力消耗路径
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] heights = {{1,2,2},{3,8,2},{5,3,5}};
        int minimumEffortPath = solution.minimumEffortPath(heights);
        System.out.println(minimumEffortPath);
    }

    int[][] arr = new int[][]{{0,-1},{0,1},{1,0},{-1,0}};
    public int minimumEffortPath(int[][] heights) {
        int row = heights.length;
        int col = heights[0].length;
        int l = 0, r = 1000010;
        // 二分模板，要得到左边的就r = mid，找中间的就 r = mid - 1
        while (l < r) {
             int mid = l + (r - l) / 2;
            if (dfs(0,0,heights,new boolean[row][col],mid)) {
                r = mid ;
            } else {
                l = mid + 1;
            }
        }
        return l;

    }

    public boolean dfs(int x,int y,int[][] a, boolean[][] visit, int target) {
        if (x == a.length-1 && y == a[0].length-1) {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            int newX = x + arr[i][0];
            int newY = y + arr[i][1];
            if (newX >= 0 && newY >= 0 && newX <= a.length-1 && newY <= a[0].length-1 && !visit[newX][newY] && Math.abs(a[x][y] - a[newX][newY]) <= target) {
                visit[newX][newY] = true;
                if ( dfs(newX,newY,a,visit,target)) {
                    return true;
                }
            }
        }
        return false;
    }
}
